TCAMs are typically used in routers and Ethernet switches for Internet protocol (IP) address forwarding. The storage elements are typically designed using a dynamic NOR/NAND type cell.
Content addressable memory (CAM) supports a read operation, write operation, and compare operation. A compare bus of the same width (e.g., bits per word) as an entry in the CAM is input at a clock edge. The data of the compare bus is simultaneously compared to every entry in the CAM. That is, the comparison occurs parallel so the bus may be compared to every entry in the CAM during one clock cycle. An entry is a match when every bit in an entry matches the corresponding bit in the compare bus. Alternatively, an entry is a mismatch when any bit in an entry does not match the corresponding bit in the compare bus. The bits of the entries in the CAM are either 0 or 1.
A TCAM is similar to CAM with the addition of a mask value that may be stored in a cell. The mask value may be referred to as a local mask. A mask value is not compared with a compare bit, and therefore, the compare result will always be a match.
FIG. 1 illustrates an architecture of a conventional TCAM 100. As illustrated in FIG. 1, a search word, such as “1101,” is input to a register 150 of the TCAM 100. The search word is compared to the value stored in the TCAM cells 110. TCAMs typically have sixteen TCAM cells per stage. The search is simultaneously conducted across the TCAM cells 110. The content of the TCAM cells 110 may be a high bit (1), a low bit (0), or a mask value (X). Prior to the search, a match line 130-136 for each set of TCAM cells 120-126 is set to high. The match lines 130-136 are input to a priority encoder 140. The TCAM 100 outputs (MLout) the address of the set of TCAM cells that match the search word line. Because the search is a parallel search, the search may be completed in one clock cycle. It should be noted that a mask value may be a 0 or 1, still, in the present disclosure, the mask value may be referred to as an X.
As an example, as illustrated in FIG. 1, a first set of TCAM cells 120 is set to “1 X 0 1,” a second set of TCAM cells 122 is set to “1 0 X 1,” a third set of TCAM cells 124 is set to “1 1 X X,” and a fourth set of TCAM cells 126 is set to “1 X 1 X.” When comparing the content of the TCAM cells to the search bit, when the content of the TCAM cell is a mask value X, the comparison will yield a match. Thus, according to the example illustrated in FIG. 1, the first set of TCAM cells 120 and the third set of TCAM cells 124 match the search word in the register 150. Accordingly, the match lines 130 134 of the first set of TCAM cells 120 and the third set of TCAM cells 124 will indicate a match and the priority encoder 140 outputs the address of the first set of TCAM cells 120 and the third set of TCAM cells 124.
The conventional TCAM architecture is a dynamic circuit and has a high dynamic power dissipation. In some cases, the TCAM may have a dynamic NAND architecture. In other cases, the TCAM may have a dynamic NOR architecture.
FIG. 2 illustrates a conventional dynamic NAND TCAM 200. As illustrated in FIG. 2, the dynamic NAND architecture 200 includes a match line MLNAND charged by a pre-charge line PRE# from a pull-up transistor 210. The match line MLNAND is connected to a series of intermediate match lines ML0-MLn-1. Each of the intermediate match lines ML0-MLn-1 is coupled to a mask cell Mask0-Maskn-1 and a key cell Key0-Keyn-1 via a transmission gate. The transmission gate includes a key NMOS transistor 202 coupled to a key cell Key0-Keyn-1 and a mask NMOS transistor 204 coupled to a mask cell Mask0-Maskn-1.
The content of the mask cells Mask0-Maskn-1 is illustrated in an expanded mask cell 222. As shown in the expanded mask cell 222, mask cells Mask0-Maskn-1 are SRAM cells including a mask value M, a mask value bar M#, a mask word line WLM, a mask bit line BLM, and a mask bit line bar BLM#. The content of the key cells Key0-Keyn-1 is illustrated in an expanded key cell 220. As shown in the expanded key cell 220, the key cells Key0-Keyn-1 are SRAM cells with XNOR logic. The key cells Key0-Keyn-1 further include a search line SL, a search line bar SL#, a key bit line BLK, a key bit line bar BLK#, a key value K, a key bar value K#, and a key write line WLK.
In a dynamic NAND TCAM architecture, the match lines are pre-charged high and evaluate low to indicate a match. That is, a pre-charge signal is used for each match line during every cycle to set the match lines to high. Depending on the status of the mask cell or key cell, the match line may be pulled low or remain high. Each intermediate match line is associated with a mask cell and a key cell. Furthermore, each key cell further includes XNOR logic. The dynamic NAND TCAM uses a serial operation. Thus, an intermediate match line (n-1) may discharge when the previous intermediate match line (n-2) is pulled low to indicate a match. That is, the operation continues from one intermediate match line (n-2) to a subsequent intermediate match line (n-1) when there is a match and stops progressing through the intermediate match lines when there is a mismatch.
In a dynamic NOR TCAM architecture, match lines are pre-charged high and evaluate low to indicate a mismatch. The majority of comparisons yield a mismatch, and therefore, the dynamic NOR has an increased power consumption as a result of switching from high to low for indicating a mismatch. Furthermore, the dynamic NOR has a complex timing control because the pre-charge signal is used by each match line in each clock cycle.
FIG. 3 illustrates a conventional dynamic NOR TCAM 300. As illustrated in FIG. 3, the dynamic NOR TCAM 300 includes key cells Key0-Keyn-1 and mask cells Mask0-Maskn-1. Typically, a NOR TCAM, such as the NOR TCAM 300 of FIG. 3, may have sixteen key and mask cells. Data is input via search lines (SL0-SLn-1 and SL0#-SLn-1#). The data is compared to the values stored in the key cells Key0-Keyn-1 and mask cells Mask0-Maskn-1. The match line MLNOR is pre-charged high via the pre-charge line PRE# from a pull-up transistor 303. The match line MLNOR will evaluate low when there is a mismatch between the data input via one of the search lines (SL0-SLn-1 and SL0#-SLn-1#) and the data stored in one of the cells Key0-Keyn-1 Mask0-Maskn-1. The match line remains high when the values of all of the cells Key0-Keyn-1 Mask0-Maskn-1 match the input data.
The structure of the key cells Key0-Keyn-1 is illustrated in the expanded key cell 330 and the structure of the mask cells Mask0-Maskn-1 is illustrated in the expanded mask cell 333. As illustrated in the expanded key cell 330, the key cells Key0-Keyn-1 are implemented via an SRAM cell. During a compare operation, the key bar K# is ANDed with the search line SL. The key cells Key0-Keyn-1 include a bit line BLK, a bit line bar BLK#, and a word line WLK.
As illustrated in the expanded mask cell 333, the mask cells Mask0-Maskn-1 are implemented via a SRAM cell. During a comparison operation, the mask bar M# is ANDed with the search line bar SL#. The mask cells Mask0-Maskn-1 include a bit line BLM, a bit line bar BLM#, and a word line WLM.
As discussed above, in a dynamic NOR TCAM, the match lines are pre-charged high at the beginning of every cycle and the match lines evaluate low to indicate a mismatch. The majority of comparisons of the cells in a TCAM yield a mismatch. Thus, the power consumption of the dynamic NOR TCAM is increased as a result of the switching from high to low when indicating a mismatch. In some cases, match lines may be pre-discharged low to reduce the power consumption. Still, even when then match lines are pre-discharged, a pre-charge operation charges the match line at the beginning of every cycle. Accordingly, the pre-charging of the match line leads to an increase in power consumption and additionally control circuitry.